The present invention relates generally to vectorized Galois field multiplication, and more specifically, to vectorized Galois field multiplication in which modified vector elements of a first input operand and vector elements of a second input operand are input into a single hardware tree configured for subdivision into staggered subtrees a size of each of which being based on the base mode size.
A Galois field multiplier performs a function that can be described as “carry-less multiplication.” That is, the operation resembles multiplication, with a bit-wise AND of two input elements, but the partial products are not added. Instead, the columns are XORed, with no carries from column to column.
An exemplary Galois field multiplier was described in U.S. Patent Application 20100306293, which was filed on May 12, 2010, the entire contents of which are incorporated herein by reference. As disclosed in that application, a Galois field multiplier includes a multiplication circuit for inputting two m bits binary multiplicators and outputting their product, where m is an integral power of 2, and the output of the multiplication circuit includes a high bits portion output and a low bits portion output. The Galois field multiplier further includes a memory for storing a Galois field multiplication coefficient array calculated from a selected Galois field primitive polynomial, a first module for performing an operation on the output of the multiplication circuit and the Galois field multiplication coefficient array stored in said memory to obtain the product of the two m bits binary multiplicators over the Galois field. The Galois field multiplier has a small hardware footprint, short response latency and strong universality.
Another exemplary Galois field multiplier was described in U.S. Pat. No. 6,023,782, which was filed on Dec. 13, 1996, the entire contents of which are incorporated herein by reference. As disclosed in that application, a circuit performs a computation of a plurality of coefficients of an error locator polynomial and a plurality of coefficients of an error evaluator polynomial in a system for correcting errors in a Reed-Solomon encoded datastream. The circuit is coupled to a syndrome generator and receives syndromes and includes an arithmetic unit iteratively generating intermediate and final values of the plurality of coefficients of an error locator polynomial and the plurality of coefficients of an error evaluator polynomial, a random access memory storing the intermediate and final values of the plurality of coefficients of an error locator polynomial and the plurality of coefficients of an error evaluator polynomial and a control unit. The control unit controls the arithmetic unit and the memory and detects when the computation of the plurality of coefficients of an error locator polynomial and the plurality of coefficients of an error evaluator polynomial has been completed.